

/**************       b_5_9_tree.c      *****************/
/*														*/
/* Description: B+ tree of char values with rank=9      */
/* Author: Xee									        */  
/* Last update: 18/12/2009	22:10						*/
/* Programmed as a part of  Operating systems HW 3      */
/*														*/
/********************************************************/

#ifndef __B_PLUS_9__
#define __B_PLUS_9__


#include <stdio.h>
#include <stdlib.h>
#define BPLUS_RANK_H 9
#define BPLUS_RANK_L 5
#define BPLUS_ROOT_RANK_L 2



#pragma region MACROS

#define ALLOCATE(var,type,LEN,error_return) \
	{if ((var=(type *)malloc(LEN * sizeof(type)))==NULL) \
	{ return (error_return);}}

// allocate a new leaf to be inserted
#define CREATE_A_NEW_LEAF(var,_data,_key,_father) \
	{ALLOCATE(var,TreeNode,1,B_OUT_OF_MEMORY) \
	 var->Data = _data; var->Key = _key; \
	 var->NType = LEAF; var->Father = _father;}

// allocate a new leaf to be inserted
#define CREATE_A_NEW_BUCKET(var,_father) \
	{ALLOCATE(var,TreeNode,1,B_OUT_OF_MEMORY) \
	var->Father = _father; var->NType = BUCKET;\
	var->CurrentRank = 0;}
#pragma endregion MACROS

#pragma region Enum Types
/* Result  - possible return values */
typedef enum {
	B_SUCCESS,
	B_BAD_ARGUMENTS,
	B_KEY_ALREADY_EXIST,
	B_KEY_NOT_EXIST, 
	B_OUT_OF_MEMORY
} Bplus_Result;

typedef enum {
	LEAF,
	BUCKET,
	ROOT
} NodeType;
#pragma endregion Enum Types

#pragma region  Bplus-5-9 structure
/********************************************************/

typedef struct tree_node_t {
	NodeType NType;
	struct tree_node_t* Father; // the father of the node
	// Relevant when NType = LEAF.
	int Key;
	char Data;
	
	// Relevant when NType = BUCKET.
	short CurrentRank;			// the current rank of the node -  means the current sons number.
	int KeysArray[BPLUS_RANK_H];				// array of the keys.
	struct tree_node_t* Sons[BPLUS_RANK_H + 1];	// array of the sons.

} TreeNode;

// The data structure that holds the Bplus tree
typedef struct b_plus_5_9_t {
	int NumOfLeaves;
	TreeNode* Root;
	TreeNode* FirstLeaf;
} Bplus5_9;

static Bplus5_9 Btree;

/********************************************************/
#pragma endregion The structs of the DS Bplus-5-9

#pragma region Auxiliary functions  

/******************************************************************/
/*                Auxiliary functions                             */
/******************************************************************/

static void ShiftKeysArrayToRight(int arr[], int index,int last_index)
{
	int from,to;
	to = last_index + 1;
	from = last_index;
	for( ;from >= index; --from,--to){
		arr[to]=arr[from];
	}
	// arr[to] is a duplicated value, we can assign to it the value
	// we want after doing ShiftRight
}
static void ShiftSonsArrayToRight(TreeNode* arr[], int index,int last_index)
{
	int from,to;
	to = last_index + 1;
	from = last_index;
	for( ;from >= index; --from,--to){
		arr[to]=arr[from];
	}
		// arr[to] is a duplicated value, we can assign to it the value
		// we want after doing ShiftRight
}
static int InsertInto(int* arr, int new_key,int last_index)
{
	int i;
	for(i=0; i <= last_index ; ++i)
	{
		if (arr[i] > new_key) break;
	}
	if (i<=last_index) ShiftKeysArrayToRight(arr,i,last_index);
	arr[i] = new_key;
	return i;
}
static Bplus_Result Aux_Find_Key(int Key,char* ValueOfFoundItem,TreeNode** ContainingBucket,int* L_Index)
{
	TreeNode *current = Btree.Root;
	int i;
	Bplus_Result SearchResult = B_KEY_NOT_EXIST;
	short Last_key_index;

	(*ContainingBucket) = NULL;
	if (Btree.NumOfLeaves == 0) return B_KEY_NOT_EXIST;
	if (Btree.NumOfLeaves == 1) {
		if (Key == Btree.FirstLeaf->Key)(*ValueOfFoundItem) = Btree.FirstLeaf->Data; 
		return  ( Key == Btree.FirstLeaf->Key ? B_SUCCESS : B_KEY_NOT_EXIST );
		
	}

	while ( current->NType != LEAF )
	{
		Last_key_index = current->CurrentRank-2;
		for(i=0; i <= Last_key_index ; ++i)
		{
			if (current->KeysArray[i] > Key) break;
		}
		// we can be sure that 'i' is the correct index.
		(*L_Index) = i;
		current = current->Sons[i];
		
	}
	// The type of 'current' is LEAF
	if (current->Key == Key)
	{
		if (current->NType != LEAF) printf (" Wtf??! There must be something wrong here \n");
		(*ValueOfFoundItem) = current->Data;
		SearchResult = B_SUCCESS;
	}
	(*ContainingBucket) = current->Father;
	return SearchResult;	
}



static Bplus_Result SplitUp(TreeNode* CorruptedBucket)
{
	TreeNode *CurrentBucket = CorruptedBucket,*RightBucket,*CommonFather;
	int i,keysArrSize,SonsArrSize,TheSeparatorKey,index;

	while (CurrentBucket != NULL){

		if ( CurrentBucket->CurrentRank <= BPLUS_RANK_H ) break;
		if (CurrentBucket->Father == NULL ){
			CREATE_A_NEW_BUCKET(CommonFather,NULL) // allocate a new father to be the common father.
			Btree.Root = CommonFather; // update the root to be the new father
		}
		else{
			CommonFather = CurrentBucket->Father;
		}

		CREATE_A_NEW_BUCKET(RightBucket,NULL) // allocate a new Bucket as a right son.
		RightBucket->CurrentRank = (CurrentBucket->CurrentRank / 2 );
		SonsArrSize = RightBucket->CurrentRank;     // in 5-9 tree, this always should be 5.
		keysArrSize = RightBucket->CurrentRank - 1; // in 5-9 tree, this always should be 4.
		TheSeparatorKey = CurrentBucket->KeysArray[BPLUS_RANK_H/2];

		for(i=0; i < keysArrSize  ; ++i) { RightBucket->KeysArray[i] = CurrentBucket->KeysArray[i+5]; }
		for(i=0; i < SonsArrSize  ; ++i) { RightBucket->Sons[i]  = CurrentBucket->Sons[i+5]; }
		for(i=0; i < SonsArrSize  ; ++i) { RightBucket->Sons[i]->Father = RightBucket; }

		CurrentBucket->CurrentRank = RightBucket->CurrentRank;

		CurrentBucket->Father = CommonFather; // attach to the new common father
		RightBucket->Father = CommonFather;   // attach to the new common father


		if( CommonFather->CurrentRank == 0) // Father is new
		{
			CommonFather->KeysArray[0] = TheSeparatorKey;
			CommonFather->Sons[0] = CurrentBucket;
			CommonFather->Sons[1] = RightBucket;
			CommonFather->CurrentRank = 2;
			goto Finsih;
		}
		//in case father was already there
		index = InsertInto(CommonFather->KeysArray, TheSeparatorKey, CommonFather->CurrentRank-2);
		ShiftSonsArrayToRight(CommonFather->Sons,index,CommonFather->CurrentRank-1);
		CommonFather->Sons[index+1] = RightBucket;
		CommonFather->CurrentRank++;


		CurrentBucket = CurrentBucket->Father;		

	}

Finsih: return B_SUCCESS;

}
#pragma endregion Aux

#pragma region Btree Interface methods 


/******************************************************************/
/*                Btree Interface methods                         */
/******************************************************************/

/*
 * Method: Bplus_Init
 * Description: Initializes the Bplus tree.
 * Returns: None.
 *
 */ 
void Bplus_Init()
{
	Btree.Root = NULL;
	Btree.FirstLeaf = NULL;
	Btree.NumOfLeaves = 0;

}



/*
 * Method: Bplus_Insert
 * Description: inserts a new given Key, with a new value.
 * Returns: B_SUCCESS if insertion was done, B_KEY_ALREADY_EXIST if the key already exists.
 *
 */    
Bplus_Result Bplus_Insert(int Key, char Value)
{
	TreeNode *new_leaf,*ToBucket;
	char return_value;
	int Actual_Index,NewKey,NewLeafIndex;
	Bplus_Result SearchResult;

	if (Btree.NumOfLeaves == 0){
	
		CREATE_A_NEW_LEAF(Btree.FirstLeaf, Value, Key, NULL)
	}

	else if (Btree.NumOfLeaves == 1){

		if (Key == Btree.FirstLeaf->Key) return B_KEY_ALREADY_EXIST;

		CREATE_A_NEW_BUCKET(Btree.Root,NULL) // allocate a new Root
			Btree.Root->CurrentRank = 2;

		CREATE_A_NEW_LEAF(new_leaf, Value, Key, Btree.Root)// allocate a new leaf
			Btree.FirstLeaf->Father = Btree.Root;

		if(new_leaf->Key > Btree.FirstLeaf->Key){
			Btree.Root->KeysArray[0] = new_leaf->Key;
			Btree.Root->Sons[0] = Btree.FirstLeaf; // let the first leaf to be the left son
			Btree.Root->Sons[1] = new_leaf; // let the new leaf to be the right son
		}
		else{
			Btree.Root->KeysArray[0] = Btree.FirstLeaf->Key;
			Btree.Root->Sons[0] = new_leaf; // let the new leaf to be the left son
			Btree.Root->Sons[1] = Btree.FirstLeaf; // let the first leaf to be the right son
		}

	}
	else{
		SearchResult = Aux_Find_Key(Key, &return_value, &ToBucket, &Actual_Index);	
		if ( SearchResult == B_SUCCESS ) return B_KEY_ALREADY_EXIST;
		
		CREATE_A_NEW_LEAF(new_leaf, Value, Key, ToBucket)
		
		NewKey = (ToBucket->Sons[Actual_Index]->Key > Key ? ToBucket->Sons[Actual_Index]->Key : Key );
			// NewKey is the max key between the key of the new leaf    AND
			//the key of the last leaf key we found in search
		InsertInto(ToBucket->KeysArray, NewKey, ToBucket->CurrentRank-2);
			// Insert the new key to the corresponding index.
		ShiftSonsArrayToRight(ToBucket->Sons,Actual_Index,ToBucket->CurrentRank-1);
			// Shift the sons array to right.
		NewLeafIndex = (ToBucket->Sons[Actual_Index]->Key > Key ? Actual_Index : Actual_Index+1 );
		ToBucket->Sons[NewLeafIndex] = new_leaf;
		ToBucket->CurrentRank++;

		if(ToBucket->CurrentRank > BPLUS_RANK_H ) 
		{
			SplitUp(ToBucket);// do the splitting Thing .. 
		}
		
	}
	Btree.NumOfLeaves++;
	return B_SUCCESS;
}




/*
 * Method: Bplus_Find
 * Description: Finds a given Key.
 * Returns: B_SUCCESS if key is found, B_KEY_NOT_EXIST else.
 *
 */                                      

Bplus_Result Bplus_Find(int Key,char* ValueOfFoundItem)
{
	TreeNode *current = Btree.Root,*CB;
	int index;
	return Aux_Find_Key(Key, ValueOfFoundItem, &CB, &index);	
}
#pragma endregion Btree Interface methods 

/********************************************************/
/********************************************************/
/*					FOR DEBUGGING						*/
/********************************************************/
/********************************************************/

#pragma region FOR DEBUGGING
// For debugging only
static void Aux_PrintTree(TreeNode* current)
{
	short Last_index;
	int i;

	if (current->NType == LEAF){
		printf ("Key: %d , Data: %c \n",current->Key,current->Data);
		return;
	}
	Last_index = current->CurrentRank-1;
	for(i=0; i <= Last_index ; ++i)
	{
		Aux_PrintTree(current->Sons[i]);
	}

}


void PrintTree()
{

	if (Btree.NumOfLeaves == 0) return ;
	if (Btree.NumOfLeaves == 1) {
		printf ("Key: %d , Data: %c \n",Btree.FirstLeaf->Key,Btree.FirstLeaf->Data);
		return;
	}
	Aux_PrintTree(Btree.Root);
	return;

}
#pragma endregion FOR DEBUGGING





#endif /* __B_PLUS_9__ */

